package CodeTop.最长公共子序列;

// https://leetcode.cn/problems/longest-common-subsequence/submissions/
// DP
class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
        int n = cs1.length, m = cs2.length;
        // dp[i][j] - 由 s1 前 i 个元素, s2 前 j 个元素构成的最长子序列的长度
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (cs1[i - 1] == cs2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        return dp[n][m];
    }
}